Network elements such as routers or switches typically utilize ACLs to implement packet filtering or other similar functions. A given ACL generally comprises a set of rules, with each rule having one or more fields and a corresponding action. The fields of the rule define a particular pattern that may be associated with a packet, such as particular source and destination addresses in the packet filtering context, with the corresponding action specifying an action that is taken if a packet matches the particular pattern. Generally, the ACL rules are scanned for each packet arriving in a router or switch to determine if a match exists between the packet and any of the patterns. Depending on the pattern matched, the corresponding action may be either to accept or to deny the packet. ACLs typically imply an ordered matching, that is, an ordered list of the rules is utilized, and the first rule in the ordered list of rules having a pattern which matches the packet is applied to that packet.
It is desirable in many high-rate packet processing applications to configure network processors to perform ACL-based packet filtering operations. A network processor generally controls the flow of packets between a physical transmission medium and a switch fabric in a router or switch. A given router or switch may include multiple network processors arranged, by way of example, in the form of an array of line or port cards with one or more of the processors associated with each of the cards.
Although network processors are becoming increasingly powerful, they nonetheless continue to face a significant challenge in providing line rate performance for ACL-based packet filtering. This challenge is attributable in large part to deficiencies associated with conventional techniques for implementing ACLs, as will be outlined below.
One such conventional technique involves the use of ternary content addressable memories (TCAMs), which are specialized memory devices incorporating on-chip logic for performing lookups. Since TCAMs utilize hardware to achieve enhanced lookup performance, they tend to be expensive to build and also consume large amounts of power. These cost and power requirements increase substantially as the number of rules and number of fields per rule in an ACL increase. TCAMs are also not very flexible in terms of storing multiple ACLs, each of which may include different arrangements of rules and fields. As a result, TCAMs may not be practical for use in a network processor.
Another conventional technique involves storing the complete set of ACL rules in a simple set of tables or other linear format, with the rules being applied sequentially to each received packet in the manner previously described. Unfortunately, this technique is also problematic in that the processing operations associated with applying the rules to each received packet are in many cases inefficient, and can thus degrade the performance of the network processor. In addition, the amount of memory required to store the rule set can be excessive, particularly as the number of rules and number of fields per rule in an ACL increase. The excessive memory requirements are particularly problematic in the network processor context, since network processors typically have limited internal memory as well as bandwidth restrictions associated with external memory accesses.
It is therefore apparent that a need exists for improved techniques for implementing an ACL, particularly in conjunction with utilization of the ACL to provide packet filtering or related functions in a network processor.